#include "Heap(堆).h"
//堆的初始化
void HeapInit(Heap* php)
{
    assert(php);
    php->arr = NULL;
    php->capacity = 0;
    php->size = 0;
}
//堆的销毁
void HeapDestroy(Heap* php)
{
    assert(php);
    free(php->arr);
    php->arr = NULL;
    php->size = 0;
    php->capacity = 0;
}
//堆的打印
void HeapPrint(Heap* php)
{
    assert(php);
    for (int i = 0; i < php->size; ++i)
    {
        printf("%d ",php->arr[i]);
    }
    printf("\n");
}
//堆的创建
void HeapCreate(Heap* php)
{
    assert(php);
    if(php->size == php->capacity)
    {
        int newCapacity = php->capacity == 0 ? 4 : (php->capacity)*2;
        int* data = (int*) realloc(php->arr,sizeof (int)*newCapacity);
        if(data == NULL)
        {
            perror("malloc fail");
            exit(-1);
        }
        php->arr = data;
        php->capacity = newCapacity;
    }
}
//堆的插入
void HeapPush(Heap* php,int x)
{
    HeapCreate(php);
    php->arr[php->size] = x;
    php->size++;
    //建立大堆
    AdjustUp(php->arr,php->size-1);
}
//堆的删除
void HeapPop(Heap* php)
{
    assert(php);
    assert(!HeapEmpty(php));
    Swap(&php->arr[0],&php->arr[php->size-1]);
    php->size--;
    AdjustDown(php->arr,0,php->size);
}
//堆的根节点
int HeapTop(Heap* php)
{
    assert(php);
    assert(!HeapEmpty(php));
    return php->arr[0];
}
//堆的节点个数
int HeapSize(Heap* php)
{
    assert(php);
    return php->size;
}
//判断堆是否为空
bool HeapEmpty(Heap* php)
{
    assert(php);
    return php->size == 0;
}
//交换
void Swap(int* x,int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
//建立大堆,向上调整
void AdjustUp(int* arr,int child)
{
    int parent = (child-1)/2;
    while (child > 0)
    {
        if(arr[child] > arr[parent])
        {
            Swap(&arr[child],&arr[parent]);
            child = parent;
            parent = (child-1)/2;
        }
        else
            break;
    }
}
//建立大堆，向下调整
void AdjustDown(int*arr,int parent,int size)
{
    int child = parent*2 + 1;
    while (child < size)
    {
        if(child + 1 < size && arr[child] < arr[child+1])
        {
            child = child + 1;
        }
        if(arr[child] > arr[parent])
        {
            Swap(&arr[child],&arr[parent]);
            parent = child;
            child = parent*2 + 1;
        }
        else
            break;
    }
}